0241. 为运算表达式设计优先级【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 分治

1. 📝 题目描述

• leetcode

给你一个由数字和运算符组成的字符串 expression，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。

生成的测试用例满足其对应输出值符合 32 位整数范围，不同结果的数量不超过 10^4。

---

示例 1：

输入：expression = "2-1-1"
输出：[0,2]
解释：
((2-1)-1) = 0
(2-(1-1)) = 2

示例 2：

输入：expression = "2*3-4*5"
输出：[-34,-14,-10,-10,10]
解释：
(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10

---

提示：

• 1 <= expression.length <= 20
• expression 由数字和算符 '+'、'-' 和 '*' 组成。
• 输入表达式中的所有整数值在范围 [0, 99]
• 输入表达式中的所有整数都没有前导 '-' 或 '+' 表示符号。

2. 🎯 s.1 - 分治

c

int* diffWaysToCompute(char* expression, int* returnSize) {
    int* res = (int*)malloc(sizeof(int) * 1000);
    *returnSize = 0;
    int len = strlen(expression);
    for (int i = 0; i < len; i++) {
        if (expression[i] == '+' || expression[i] == '-' || expression[i] == '*') {
            char leftStr[len + 1], rightStr[len + 1];
            strncpy(leftStr, expression, i);
            leftStr[i] = '\0';
            strcpy(rightStr, expression + i + 1);
            int leftSize, rightSize;
            int* left = diffWaysToCompute(leftStr, &leftSize);
            int* right = diffWaysToCompute(rightStr, &rightSize);
            for (int l = 0; l < leftSize; l++) {
                for (int r = 0; r < rightSize; r++) {
                    if (expression[i] == '+') res[(*returnSize)++] = left[l] + right[r];
                    else if (expression[i] == '-') res[(*returnSize)++] = left[l] - right[r];
                    else res[(*returnSize)++] = left[l] * right[r];
                }
            }
            free(left);
            free(right);
        }
    }
    if (*returnSize == 0) res[(*returnSize)++] = atoi(expression);
    return res;
}

js

/**
 * @param {string} expression
 * @return {number[]}
 */
var diffWaysToCompute = function (expression) {
  const res = []
  for (let i = 0; i < expression.length; i++) {
    const ch = expression[i]
    if (ch === '+' || ch === '-' || ch === '*') {
      const left = diffWaysToCompute(expression.slice(0, i))
      const right = diffWaysToCompute(expression.slice(i + 1))
      for (const l of left) {
        for (const r of right) {
          if (ch === '+') res.push(l + r)
          else if (ch === '-') res.push(l - r)
          else res.push(l * r)
        }
      }
    }
  }
  if (res.length === 0) res.push(Number(expression))
  return res
}

py

class Solution:
    def diffWaysToCompute(self, expression: str) -> List[int]:
        res = []
        for i, ch in enumerate(expression):
            if ch in '+-*':
                left = self.diffWaysToCompute(expression[:i])
                right = self.diffWaysToCompute(expression[i + 1:])
                for l in left:
                    for r in right:
                        if ch == '+':
                            res.append(l + r)
                        elif ch == '-':
                            res.append(l - r)
                        else:
                            res.append(l * r)
        if not res:
            res.append(int(expression))
        return res

• 时间复杂度：$O(C_n)$（卡特兰数），其中 $n$ 是运算符个数
• 空间复杂度：$O(C_n)$，存储所有可能的结果

算法思路：

• 以每个运算符为分割点，递归计算左右两侧所有可能的结果
• 将左右结果两两组合计算，基本情况为纯数字